public class NthTribonacciNumber {
    public int tribonacci(int n) {
        // 特殊值的判定
        if(n == 0) {
            return 0;
        }
        if(n == 1 || n == 2) {
            return 1;
        }
        // 该题的状态表示为: dp表中每个元素的值就是对应泰波那契数列的值
        // 1.构造dp表(这里的范围给出是 0 <= n <= 37, 因此 dp 表大小为 n+1)
        int[] dp = new int[n+1];

        // 2.根据状态转移方程来填表
        // 该题的状态转移方程为 dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        // 注意越界问题
        // 2.1 初始化(防止越界问题, 这里题目已给出前面三项的值)
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        // 2.2 填表
        for(int i = 3; i < n+1; i++) {
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }

        // 3.根据构造好的dp表输出结果
        return dp[n];
    }

    public int tribonacci1(int n) {
        // 处理边界情况
        if(n == 0) {
            return 0;
        }
        if(n == 1 || n == 2) {
            return 1;
        }

        // 定义4个变量, 来进行空间优化, 其中 abc 就是泰波那契的前三个数, d为要求出的目标泰波那契数
        int a = 0, b = 1, c = 1;
        int d = 2;

        // 滚动 n-3 次就能得出答案
        while(n - 3 != 0) {
            // 滚动操作
            a = b;
            b = c;
            c = d;

            // 求出 d
            d = a + b + c;
            n--;
        }

        return d;
    }
}
